#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <ctype.h>
#include <assert.h>

#include "listz.h"
#include "jeffz.h"
#include "utilz.h"
#include "rankz.h"

static int factorial[] = { 1, 1, 1 * 2, 1 * 2 * 3, 1 * 2 * 3 * 4, 1 * 2 * 3 * 4 * 5, 1 * 2 * 3 * 4 * 5 * 6, 1 * 2 * 3 * 4 * 5 * 6 * 7, 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8, 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9, 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10, 1 * 2 * 3 * 4
            * 5 * 6 * 7 * 8 * 9 * 10 * 11, 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 * 11 * 12, };

int Pnm(int n, int m)
{ /*[ s = n*n-1*n-2*...*n-m+1 ]*/
   int i, s = 1;
   assert(n >= 0 || m >= 0);
   if (n < m) return 0;

   for (i = n; i > n - m; i--)
      s *= i;

   return s;
}

int Ann(int n)
{ /*[ s = n*n-1*...*1 ]*/
   assert(n >= 0);
   if (n >= 0 && n <= 12) return factorial[n];
   return Pnm(n, n);
}

int Cnm(int n, int m)
{ /*[ s = n*n-1*n-2*...*n-m+1 / m*m-1*...*1 ]*/
   int i, s = 1, d = 1;
   assert(n >= 0 || m >= 0);
   if (n < m) return 0;

   m = n - m >= m ? m : n - m;

   for (i = n; i > n - m; i--)
      s *= i;

   for (i = 1; i < m + 1; i++)
      d *= i;

   return s / d;
}

int seq_2_idx(int seq[], int n)
{
   int i, r = 0;
   assert(&seq);
   assert(n >= 0);
   if (n > 12) return -1;

   for (i = 0; i < n - 1; ++i) {
      int c = 0, j = i;
      while (++j < n)
         if (seq[i] > seq[j]) c++;

      r += c * factorial[n - 1 - i];
   }
   return r;
}

int idx_2_seq(int seq[], int n, int idx)
{
   int i, j;
   int b[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
   assert(&seq);
   assert(n >= 0);
   assert(&idx);
   if (n > 12) return -1;

   for (i = 0; i < n; ++i) {
      int u = factorial[n - 1 - i];
      int c = idx / u;
      idx = idx - c * u;

      j = -1;
      do {
         j++;
         while (b[j] == -1)
            j++;
      } while (c--);
      seq[i] = b[j];
      b[j] = -1;
   }
   return 1;
}

void seq_gen(int seq[], int n, int x, void (*cb)(int*, int, int))
{
   int i;
   assert(&seq);
   assert(n >= 0);
   assert(&x);
   assert(&cb);
   if (x == n - 1) {
      int idx = seq_2_idx(seq, n);
      cb(seq, n, idx);
      return;
   }
   for (i = 0; i < n - x; i++) {
      int b[12];
      memcpy(b, seq, n * 4);
      __swap(int, b[x], b[x+i]);
      seq_gen(b, n, x + 1, cb);
   }
}

void seq_rand(int seq[], int n)
{
   int i;
   assert(&seq);
   assert(n >= 0);
   for (i = 0; i < n; i++) {
      int r = rand() % n;
      __swap(int, seq[i], seq[r]);
   }
}

////////////////

#define NGX_SLAB_PAGE_MASK   3
#define NGX_SLAB_PAGE        0
#define NGX_SLAB_BIG         1
#define NGX_SLAB_EXACT       2
#define NGX_SLAB_SMALL       3

#if (4 == 4)

#define NGX_SLAB_PAGE_FREE   0
#define NGX_SLAB_PAGE_BUSY   0xffffffff
#define NGX_SLAB_PAGE_START  0x80000000

#define NGX_SLAB_SHIFT_MASK  0x0000000f
#define NGX_SLAB_MAP_MASK    0xffff0000
#define NGX_SLAB_MAP_SHIFT   16

#define NGX_SLAB_BUSY        0xffffffff

#else /* (NGX_PTR_SIZE == 8) */

#define NGX_SLAB_PAGE_FREE   0
#define NGX_SLAB_PAGE_BUSY   0xffffffffffffffff
#define NGX_SLAB_PAGE_START  0x8000000000000000

#define NGX_SLAB_SHIFT_MASK  0x000000000000000f
#define NGX_SLAB_MAP_MASK    0xffffffff00000000
#define NGX_SLAB_MAP_SHIFT   32

#define NGX_SLAB_BUSY        0xffffffffffffffff

#endif

static ngx_slab_page_t *ngx_slab_alloc_pages(ngx_slab_pool_t *pool, unsigned pages);
static void ngx_slab_free_pages(ngx_slab_pool_t *pool, ngx_slab_page_t *page, unsigned pages);

#define ___ALIGN_UP(size, n)  (((size)+((n)-1))&(~((n)-1)))

#define ngx_pagesize  4096
//2,4,8,16,32,64,128,256,512,1024,2048,4096
static unsigned ngx_slab_min_size;
static unsigned ngx_slab_min_shift;
static unsigned ngx_slab_max_size;
static unsigned ngx_slab_max_shift;
static unsigned ngx_slab_exact_size;
static unsigned ngx_slab_exact_shift;

ngx_slab_pool_t* ngx_slab_init(unsigned char *chunk, unsigned size)
{
   unsigned char *p;
   unsigned i, smalls, pages;
   ngx_slab_page_t *smallz;
   ngx_slab_pool_t *pool;

   ngx_slab_min_shift = 3;
   ngx_slab_min_size = 1 << ngx_slab_min_shift;

   ngx_slab_max_size = ngx_pagesize / 2;
   ngx_slab_exact_size = ngx_pagesize / (8 * sizeof(unsigned long));
   for (i = ngx_slab_exact_size; i >>= 1; ngx_slab_exact_shift++) {
   }

   p = chunk;
   pool = (ngx_slab_pool_t *) p;
   pool->end = p + size;
   pages = (unsigned) ((size - sizeof(ngx_slab_pool_t)) / (ngx_pagesize + sizeof(ngx_slab_page_t)));
   pool->start = p + pages * sizeof(ngx_slab_page_t);
   pool->start = (unsigned char*)___ALIGN_UP((unsigned)pool->start, ngx_pagesize);
   pages = (unsigned) ((pool->end - pool->start) / ngx_pagesize);

   p += sizeof(ngx_slab_pool_t);
   smallz = (ngx_slab_page_t *) p;
   smalls = ngx_slab_max_shift - ngx_slab_min_shift;
   for (i = 0; i < smalls; i++) {
      smallz[i].slab = 0;
      list_init(&smallz[i].link);
   }

   p += smalls * sizeof(ngx_slab_page_t);
   pool->pagez = (ngx_slab_page_t *) p;
   memset(pool->pagez, 0, (pages - smalls) * sizeof(ngx_slab_page_t));

   list_init(&pool->free);
   pool->pagez[0].slab = pages - smalls;
   list_add_tail(&pool->free, &pool->pagez[0].link);

   return pool;
}

#if 0

void *
ngx_slab_alloc(ngx_slab_pool_t *pool, size_t size)
{
   void *p;

   ngx_shmtx_lock(&pool->mutex);

   p = ngx_slab_alloc_locked(pool, size);

   ngx_shmtx_unlock(&pool->mutex);

   return p;
}

void *
ngx_slab_alloc_locked(ngx_slab_pool_t *pool, size_t size)
{
   size_t s;
   uintptr_t p, n, m, mask, *bitmap;
   ngx_uint_t i, slot, shift, map;
   ngx_slab_page_t *page, *prev, *slots;

   if (size >= ngx_slab_max_size) {

      ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0,
                  "slab alloc: %uz", size);

      page = ngx_slab_alloc_pages(pool, (size >> ngx_pagesize_shift)
                  + ((size % ngx_pagesize) ? 1 : 0));
      if (page) {
         p = (page - pool->pages) << ngx_pagesize_shift;
         p += (uintptr_t) pool->start;

      } else {
         p = 0;
      }

      goto done;
   }

   if (size > pool->min_size) {
      shift = 1;
      for (s = size - 1; s >>= 1; shift++) { /* void */}
      slot = shift - pool->min_shift;

   } else {
      size = pool->min_size;
      shift = pool->min_shift;
      slot = 0;
   }

   ngx_log_debug2(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0,
               "slab alloc: %uz slot: %ui", size, slot);

   slots = (ngx_slab_page_t *) ((u_char *) pool + sizeof(ngx_slab_pool_t));
   page = slots[slot].next;

   if (page->next != page) {

      if (shift < ngx_slab_exact_shift) {

         do {
            p = (page - pool->pages) << ngx_pagesize_shift;
            bitmap = (uintptr_t *) (pool->start + p);

            map = (1 << (ngx_pagesize_shift - shift))
            / (sizeof(uintptr_t) * 8);

            for (n = 0; n < map; n++) {

               if (bitmap[n] != NGX_SLAB_BUSY) {

                  for (m = 1, i = 0; m; m <<= 1, i++) {
                     if ((bitmap[n] & m)) {
                        continue;
                     }

                     bitmap[n] |= m;

                     i = ((n * sizeof(uintptr_t) * 8) << shift)
                     + (i << shift);

                     if (bitmap[n] == NGX_SLAB_BUSY) {
                        for (n = n + 1; n < map; n++) {
                           if (bitmap[n] != NGX_SLAB_BUSY) {
                              p = (uintptr_t) bitmap + i;

                              goto done;
                           }
                        }

                        prev = (ngx_slab_page_t *)
                        (page->prev & ~NGX_SLAB_PAGE_MASK);
                        prev->next = page->next;
                        page->next->prev = page->prev;

                        page->next = NULL;
                        page->prev = NGX_SLAB_SMALL;
                     }

                     p = (uintptr_t) bitmap + i;

                     goto done;
                  }
               }
            }

            page = page->next;

         }while (page);

      } else if (shift == ngx_slab_exact_shift) {

         do {
            if (page->slab != NGX_SLAB_BUSY) {

               for (m = 1, i = 0; m; m <<= 1, i++) {
                  if ((page->slab & m)) {
                     continue;
                  }

                  page->slab |= m;

                  if (page->slab == NGX_SLAB_BUSY) {
                     prev = (ngx_slab_page_t *)
                     (page->prev & ~NGX_SLAB_PAGE_MASK);
                     prev->next = page->next;
                     page->next->prev = page->prev;

                     page->next = NULL;
                     page->prev = NGX_SLAB_EXACT;
                  }

                  p = (page - pool->pages) << ngx_pagesize_shift;
                  p += i << shift;
                  p += (uintptr_t) pool->start;

                  goto done;
               }
            }

            page = page->next;

         }while (page);

      } else { /* shift > ngx_slab_exact_shift */

         n = ngx_pagesize_shift - (page->slab & NGX_SLAB_SHIFT_MASK);
         n = 1 << n;
         n = ((uintptr_t) 1 << n) - 1;
         mask = n << NGX_SLAB_MAP_SHIFT;

         do {
            if ((page->slab & NGX_SLAB_MAP_MASK) != mask) {

               for (m = (uintptr_t) 1 << NGX_SLAB_MAP_SHIFT, i = 0;
                           m & mask;
                           m <<= 1, i++)
               {
                  if ((page->slab & m)) {
                     continue;
                  }

                  page->slab |= m;

                  if ((page->slab & NGX_SLAB_MAP_MASK) == mask) {
                     prev = (ngx_slab_page_t *)
                     (page->prev & ~NGX_SLAB_PAGE_MASK);
                     prev->next = page->next;
                     page->next->prev = page->prev;

                     page->next = NULL;
                     page->prev = NGX_SLAB_BIG;
                  }

                  p = (page - pool->pages) << ngx_pagesize_shift;
                  p += i << shift;
                  p += (uintptr_t) pool->start;

                  goto done;
               }
            }

            page = page->next;

         }while (page);
      }
   }

   page = ngx_slab_alloc_pages(pool, 1);

   if (page) {
      if (shift < ngx_slab_exact_shift) {
         p = (page - pool->pages) << ngx_pagesize_shift;
         bitmap = (uintptr_t *) (pool->start + p);

         s = 1 << shift;
         n = (1 << (ngx_pagesize_shift - shift)) / 8 / s;

         if (n == 0) {
            n = 1;
         }

         bitmap[0] = (2 << n) - 1;

         map = (1 << (ngx_pagesize_shift - shift)) / (sizeof(uintptr_t) * 8);

         for (i = 1; i < map; i++) {
            bitmap[i] = 0;
         }

         page->slab = shift;
         page->next = &slots[slot];
         page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_SMALL;

         slots[slot].next = page;

         p = ((page - pool->pages) << ngx_pagesize_shift) + s * n;
         p += (uintptr_t) pool->start;

         goto done;

      } else if (shift == ngx_slab_exact_shift) {

         page->slab = 1;
         page->next = &slots[slot];
         page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_EXACT;

         slots[slot].next = page;

         p = (page - pool->pages) << ngx_pagesize_shift;
         p += (uintptr_t) pool->start;

         goto done;

      } else { /* shift > ngx_slab_exact_shift */

         page->slab = ((uintptr_t) 1 << NGX_SLAB_MAP_SHIFT) | shift;
         page->next = &slots[slot];
         page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_BIG;

         slots[slot].next = page;

         p = (page - pool->pages) << ngx_pagesize_shift;
         p += (uintptr_t) pool->start;

         goto done;
      }
   }

   p = 0;

   done:

   ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0, "slab alloc: %p", p);

   return (void *) p;
}

void
ngx_slab_free(ngx_slab_pool_t *pool, void *p)
{
   ngx_shmtx_lock(&pool->mutex);

   ngx_slab_free_locked(pool, p);

   ngx_shmtx_unlock(&pool->mutex);
}

void
ngx_slab_free_locked(ngx_slab_pool_t *pool, void *p)
{
   size_t size;
   uintptr_t slab, m, *bitmap;
   ngx_uint_t n, type, slot, shift, map;
   ngx_slab_page_t *slots, *page;

   ngx_log_debug1(NGX_LOG_DEBUG_ALLOC, ngx_cycle->log, 0, "slab free: %p", p);

   if ((u_char *) p < pool->start || (u_char *) p > pool->end) {
      ngx_slab_error(pool, NGX_LOG_ALERT, "ngx_slab_free(): outside of pool");
      goto fail;
   }

   n = ((u_char *) p - pool->start) >> ngx_pagesize_shift;
   page = &pool->pages[n];
   slab = page->slab;
   type = page->prev & NGX_SLAB_PAGE_MASK;

   switch (type) {

      case NGX_SLAB_SMALL:

      shift = slab & NGX_SLAB_SHIFT_MASK;
      size = 1 << shift;

      if ((uintptr_t) p & (size - 1)) {
         goto wrong_chunk;
      }

      n = ((uintptr_t) p & (ngx_pagesize - 1)) >> shift;
      m = (uintptr_t) 1 << (n & (sizeof(uintptr_t) * 8 - 1));
      n /= (sizeof(uintptr_t) * 8);
      bitmap = (uintptr_t *) ((uintptr_t) p & ~(ngx_pagesize - 1));

      if (bitmap[n] & m) {

         if (page->next == NULL) {
            slots = (ngx_slab_page_t *)
            ((u_char *) pool + sizeof(ngx_slab_pool_t));
            slot = shift - pool->min_shift;

            page->next = slots[slot].next;
            slots[slot].next = page;

            page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_SMALL;
            page->next->prev = (uintptr_t) page | NGX_SLAB_SMALL;
         }

         bitmap[n] &= ~m;

         n = (1 << (ngx_pagesize_shift - shift)) / 8 / (1 << shift);

         if (n == 0) {
            n = 1;
         }

         if (bitmap[0] & ~(((uintptr_t) 1 << n) - 1)) {
            goto done;
         }

         map = (1 << (ngx_pagesize_shift - shift)) / (sizeof(uintptr_t) * 8);

         for (n = 1; n < map; n++) {
            if (bitmap[n]) {
               goto done;
            }
         }

         ngx_slab_free_pages(pool, page, 1);

         goto done;
      }

      goto chunk_already_free;

      case NGX_SLAB_EXACT:

      m = (uintptr_t) 1 <<
      (((uintptr_t) p & (ngx_pagesize - 1)) >> ngx_slab_exact_shift);
      size = ngx_slab_exact_size;

      if ((uintptr_t) p & (size - 1)) {
         goto wrong_chunk;
      }

      if (slab & m) {
         if (slab == NGX_SLAB_BUSY) {
            slots = (ngx_slab_page_t *)
            ((u_char *) pool + sizeof(ngx_slab_pool_t));
            slot = ngx_slab_exact_shift - pool->min_shift;

            page->next = slots[slot].next;
            slots[slot].next = page;

            page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_EXACT;
            page->next->prev = (uintptr_t) page | NGX_SLAB_EXACT;
         }

         page->slab &= ~m;

         if (page->slab) {
            goto done;
         }

         ngx_slab_free_pages(pool, page, 1);

         goto done;
      }

      goto chunk_already_free;

      case NGX_SLAB_BIG:

      shift = slab & NGX_SLAB_SHIFT_MASK;
      size = 1 << shift;

      if ((uintptr_t) p & (size - 1)) {
         goto wrong_chunk;
      }

      m = (uintptr_t) 1 << ((((uintptr_t) p & (ngx_pagesize - 1)) >> shift)
                  + NGX_SLAB_MAP_SHIFT);

      if (slab & m) {

         if (page->next == NULL) {
            slots = (ngx_slab_page_t *)
            ((u_char *) pool + sizeof(ngx_slab_pool_t));
            slot = shift - pool->min_shift;

            page->next = slots[slot].next;
            slots[slot].next = page;

            page->prev = (uintptr_t) &slots[slot] | NGX_SLAB_BIG;
            page->next->prev = (uintptr_t) page | NGX_SLAB_BIG;
         }

         page->slab &= ~m;

         if (page->slab & NGX_SLAB_MAP_MASK) {
            goto done;
         }

         ngx_slab_free_pages(pool, page, 1);

         goto done;
      }

      goto chunk_already_free;

      case NGX_SLAB_PAGE:

      if ((uintptr_t) p & (ngx_pagesize - 1)) {
         goto wrong_chunk;
      }

      if (slab == NGX_SLAB_PAGE_FREE) {
         ngx_slab_error(pool, NGX_LOG_ALERT,
                     "ngx_slab_free(): page is already free");
         goto fail;
      }

      if (slab == NGX_SLAB_PAGE_BUSY) {
         ngx_slab_error(pool, NGX_LOG_ALERT,
                     "ngx_slab_free(): pointer to wrong page");
         goto fail;
      }

      n = ((u_char *) p - pool->start) >> ngx_pagesize_shift;
      size = slab & ~NGX_SLAB_PAGE_START;

      ngx_slab_free_pages(pool, &pool->pages[n], size);

      ngx_slab_junk(p, size << ngx_pagesize_shift);

      return;
   }

   /* not reached */

   return;

   done:

   ngx_slab_junk(p, size);

   return;

   wrong_chunk:

   ngx_slab_error(pool, NGX_LOG_ALERT,
               "ngx_slab_free(): pointer to wrong chunk");

   goto fail;

   chunk_already_free:

   ngx_slab_error(pool, NGX_LOG_ALERT,
               "ngx_slab_free(): chunk is already free");

   fail:

   return;
}

static ngx_slab_page_t *
ngx_slab_alloc_pages(ngx_slab_pool_t *pool, ngx_uint_t pages)
{
   ngx_slab_page_t *page, *p;

   for (page = pool->free.next; page != &pool->free; page = page->next) {

      if (page->slab >= pages) {

         if (page->slab > pages) {
            page[pages].slab = page->slab - pages;
            page[pages].next = page->next;
            page[pages].prev = page->prev;

            p = (ngx_slab_page_t *) page->prev;
            p->next = &page[pages];
            page->next->prev = (uintptr_t) &page[pages];

         } else {
            p = (ngx_slab_page_t *) page->prev;
            p->next = page->next;
            page->next->prev = page->prev;
         }

         page->slab = pages | NGX_SLAB_PAGE_START;
         page->next = NULL;
         page->prev = NGX_SLAB_PAGE;

         if (--pages == 0) {
            return page;
         }

         for (p = page + 1; pages; pages--) {
            p->slab = NGX_SLAB_PAGE_BUSY;
            p->next = NULL;
            p->prev = NGX_SLAB_PAGE;
            p++;
         }

         return page;
      }
   }

   ngx_slab_error(pool, NGX_LOG_CRIT, "ngx_slab_alloc() failed: no memory");

   return NULL;
}

static void
ngx_slab_free_pages(ngx_slab_pool_t *pool, ngx_slab_page_t *page,
            ngx_uint_t pages)
{
   ngx_slab_page_t *prev;

   page->slab = pages--;

   if (pages) {
      ngx_memzero(&page[1], pages * sizeof(ngx_slab_page_t));
   }

   if (page->next) {
      prev = (ngx_slab_page_t *) (page->prev & ~NGX_SLAB_PAGE_MASK);
      prev->next = page->next;
      page->next->prev = page->prev;
   }

   page->prev = (uintptr_t) &pool->free;
   page->next = pool->free.next;

   page->next->prev = (uintptr_t) page;

   pool->free.next = page;
}

#endif
